#include <bits/stdc++.h>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    // ListNode *removeElements(ListNode *head, int val)
    // {
    //     ListNode *res = head;

    //     while (res != nullptr && res->val == val)
    //     {
    //         res = res->next;
    //     }

    //     if (res == nullptr)
    //     {
    //         return res;
    //     }

    //     ListNode *front = res;
    //     ListNode *cur = res->next;

    //     while (cur != nullptr)
    //     {
    //         if (cur->val == val)
    //         {
    //             front->next = cur->next;
    //             cur = cur->next;
    //             continue;
    //         }
    //         front = cur;
    //         cur = cur->next;
    //     }
    //     return res;
    // }

    // method 1
    //  ListNode *removeElements(ListNode *head, int val)
    //  {
    //      while (head != nullptr && head->val == val)
    //      {
    //          ListNode *tmp = head;
    //          head = head->next;
    //          delete tmp;
    //      }

    //     ListNode *cur = head;
    //     while (cur != nullptr && cur->next != nullptr)
    //     {
    //         if (cur->next->val == val)
    //         {
    //             ListNode *tmp = cur->next;
    //             cur->next = cur->next->next;
    //             delete tmp;
    //         }
    //         else
    //         {
    //             cur = cur->next;
    //         }
    //     }
    //     return head;
    // }

    // mtehod 2
    ListNode *removeElements(ListNode *head, int val)
    {
        ListNode *dummy_head = new ListNode(0);
        dummy_head->next = head;
        ListNode *cur = dummy_head;
        while (cur->next != nullptr)
        {
            if (cur->next->val == val)
            {
                ListNode *tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else
            {
                cur = cur->next;
            }
        }
        head = dummy_head->next;
        delete dummy_head;
        return head;
    }
};

int main()
{
    ListNode *tail = new ListNode(6);
    ListNode *node1 = new ListNode(5, tail);
    ListNode *node2 = new ListNode(4, node1);
    ListNode *node3 = new ListNode(3, node2);
    ListNode *node4 = new ListNode(6, node3);
    ListNode *node5 = new ListNode(2, node4);
    ListNode *head = new ListNode(1, node5);

    Solution sol;

    ListNode *res = sol.removeElements(head, 6);

    while (res->next != nullptr)
    {
        int value = res->val;
        printf("%d ", value);
        res = res->next;
    }

    printf("%d\n", res->val);

    return 0;
}